1. Field of the Invention
The present invention generally relates to memory systems for image processing systems; and more particularly to memory systems for image processing operations which require that a digitized image or partial image array be stored in a memory system that permits access to p.times.q (block), 1.times.pq (horizontal sequence), and pq.times.1 (vertical sequence) subarrays of the digitized image array, where p and q are design parameters.
2. Description of the Related Art
In general, many image data, such as analog image signals from a TV camera which can be converted into digital signals by an A/D converter, are processed by an image processor or a computer. An image can be represented by a two-dimensional array of image points, which are sets of integers that each describes the color and intensity of a portion of the image. These image data are first stored in a memory system, and then, are retrieved from the memory system to be processed by an image processor or computer.
If image data in a desired subarray are stored in the same memory module within the memory system, serial access to these data may slow down the image processing operations because one memory module can respond only to one access at a given time. Because there are many image points to be processed, a special memory system is required to reduce the overall access time. In image processing, frequently used shapes of subarrays are horizontal sequence (1.times.pq), vertical sequence (pq.times.1), and block (p.times.q), where p and q are design parameters. In order to reduce overall access time of these data, several authors have studied methods which distribute many data in different memory modules and which access these data in parallel.
A number of authors have described several methods that permit simultaneous access to data elements in a row, a column, a diagonal, and/or a rectangular area of a two-dimensional array. See the following publications: C. D. Coleman, et al, "Bank of Memories System for Multiword Access", IBM Technical Disclosure Bulletin, Vol. 9, pp. 1182-1183, February 1967; A. Weinberger, "Multiword, Multidirectional Random Access Memory System", IBM Technical Disclosure Bulletin, Vol. 10, pp. 997-998, December 1967; D. J. Kuck, "ILLIAC IV Software and Application Programming", IEEE Transactions Computers, Vol. C-17, pp. 758-770, August, 1968; D. H. Lawrie, "Access and Alignment of Data in an Array Processor", IEEE Transactions Computers, Vol. C-24, pp. 1145-1155, December, 1975; D. C. Van Voorhis et al., "Memory Systems for Image Processing, IEEE Transactions Computers, Vol. C-27, pp. 113-125, February, 1978; B. C. Lee et al., "A Study on the Image Processor Memory Architecture", Proceedings International Computer Symposium 1980, Vol. II, pp. 954-960; P. Budnik et al., and "The Organization and Use of Parallel Memories", IEEE Transactions Computers, Vol. C-20, pp. 1566-1569, December 1971.
In particular, the Van Voorhis et al article discloses several memory systems which permit simultaneous access to image points in a row, a column and a rectangular area of an image array. Such simultaneous access is necessary for many image processing operations. Van Voorhis et al essentially solved the problem of deciding how to assign image points to memory locations. The Van Voorhis et al article discusses: (1) six memory module assignment functions which distribute the image points among memory modules; (2) two address assignment functions which determine the addresses of the image points; and (3) circuitry that both calculates the addresses within memory modules simultaneously and routes these addresses to the memory modules. The memory module assignment functions provide memory systems with m=pq+1, 2pq and pq.sup.2 memory modules. In order to speed up the memory system, Van Voorhis et al have restricted all of the parameters p, q and s of the function to powers of two.
However, the Van Voorhis et al article discloses that the memory system with m=pq+1 memory modules requires a number of modulo-(pq+1) operations and that these operations may make the described system too slow for some applications. The memory systems with m=2pq and pq.sup.2 are suggested by Van Voorhis et al in order to avoid divisions (and modulo operations) involving a divisor that is not a power of 2. Because these two memory systems require many memory modules and many hardware components in the circuitry (the addressing circuitry calculates m addresses), they have the disadvantages of high hardware cost and high complexity in controlling the route and enabling circuitry.